/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-08-13
 * Time:16:08
 */
//数组练习及Arrays工具类的使用
import java.util.Arrays;
public class Test {
    public static void main(String[] args) {
        //给一个整数数组arr,判断数组中是否存在连续三个元素都是奇数的情况，如果存在，请返回true，否则返回false
        //思路：设置一个计数器count，如果是在遍历时，是奇数就置为1，偶数就置为0
        //例如：如果开始遍历时第一个元素是奇数，count=1，下一个也是奇数，count=2，再下一个如果是偶数，则count=0，再继续向下遍历，
        //直到出现count=3，则说明有三个连续的奇数，如果count没有等于3，则说明没有
        int[] arr = {1,2,34,3,4,5,7,23,12};
        System.out.println(fun4(arr));
    }
    public static boolean fun4(int[] arr){
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 != 0){
                count++;
                if (count == 3){
                    return true;
                }
            }else {
                count = 0;
            }
        }
        return false;
    }
    public static void main11(String[] args) {
        //给定一个大小为n的数组，找到其中的多数元素，多数元素是指在数组中出现次数大于 n/2 的元素
        //思路：摩尔投票算法---通过不同元素之间的相互抵消，最终剩下的候选元素即为多数元素
        int[] array = {2,2,1,1,1,2,2};
        System.out.println(fun3(array));
    }
    public static int fun3(int[] array){
        int candidate = array[0];//设置候选元素 candidate 为数组的第一个元素，计数器 count 为1
        int count = 1;
        for (int i = 1; i < array.length; i++) { //从第二个元素开始遍历数组
            if(count == 0){  //如果 count 减为0，则将下一个元素设为新的 candidate，并将 count 重置为1
                candidate = array[i];
                count = 1;
            } else if (candidate == array[i]) {  //如果当前元素等于 candidate，则 count 加1
                count++;
            }else {      //否则，count 减1
                count--;
            }
        }
        return candidate;//遍历结束后 candidate 即为多数元素
    }
    public static void main10(String[] args) {
        //单身狗：给一个非空整数数组，除了某元素只出现一次之外，其余每个元素均出现两次，找出只出现一次的元素
        //思路:将数组的每一个元素都进行按位异或^（相同为0，相异为1，0^n=n n^n=0）
        int[] array = {1,1,2,2,3};
        System.out.println(fun2(array));
    }
    public static int fun2(int[] array){
        int ret = 0;
        for (int i = 0; i < array.length; i++) {
            ret ^= array[i];
        }
        return ret;
    }
    public static void main9(String[] args) {
        //给定一个整数数组nums和一个整数目标值target，找出该数组和为target的那两个整数，并返回它们的下标
        //假设每种输入只会对应一个答案，数组中同一个元素在答案中不会重复出现
        //思路：创建一个新的数组，将两个元素的下标存放在数组中，首先从数组的第一个元素开始，除了它之外的元素都和它一个个相加，如果遍历
        //完，没有找到，则i++，j++，继续重复上面的操作
        int[] array = {2,7,11,15};
        int[] ret = fun1(array,9);
        System.out.println(Arrays.toString(ret));
    }
    public static int[] fun1(int[] array,int target){
        int[] ret = new int[]{-1,-1};//如果遍历完没有和为target的两个元素，则直接返回这个初始值
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if (array[i] + array[j] == target){
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }
        return ret;
    }
    public static void main8(String[] args) {
        //调整数组顺序使得奇数位于偶数之前，调整之后，不关心大小顺序
        //思路：设定两个下标, 分别指向第一个元素left和最后一个元素right,如果left在走的过程中发现是奇数，则++，而right在走的过程中
        //发现是偶数，则++，如果都不是这些情况，就需要进行交换
        int[] array = {1,2,3,4,5,6};
        fun(array);
        System.out.println(Arrays.toString(array));
    }
    public static void fun(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left < right){
            while (left < right && array[left] % 2 != 0){
                left++;
            }
            while (left < right && array[right] % 2 == 0){
                right--;
            }
            swap(array,left,right);
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void main7(String[] args) {
        //数组拷贝--给定一个数组, 将里面的元素逆序排列
        //思路：设定两个下标, 分别指向第一个元素和最后一个元素. 交换两个位置的元素，然后让前一个下标自增, 后一个下标自减, 循环继续即可
        int[] array = {1,2,3,4,5,6};
        System.out.print("逆序前的数组:");
        System.out.println(Arrays.toString(array));
        reverse(array);
        System.out.print("逆序后的数组:");
        System.out.println(Arrays.toString(array));
    }
    public static void reverse(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left < right){
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
            left++;
            right--;
        }
    }
    public static void main6(String[] args) {
        int[] array1 = {1,2,3,4,5,6};
        int[] array2 = {1,2,3,4,5,6};
        System.out.println(array1 == array2);//返回的是false，因为两个引用数组的地址不同

        //Arrays.equals-如果两个指定的[基本类型]数组彼此 相等 ，则返回 true
        boolean flag = Arrays.equals(array1,array2);
        System.out.println(flag);//true

        //Arrays.fill - 将指定的[基本类型]值分配给指定的[基本类型]数组的每个元素
        int[] ret = new int[10];
        Arrays.fill(ret,-1);
        System.out.println(Arrays.toString(ret));
        //指定范围
        Arrays.fill(ret,1,4,8);
        System.out.println(Arrays.toString(ret));
    }
    public static void main5(String[] args) {
        //数组拷贝
        int[] array = {1,2,31,4,15};
        int[] copy = copyArray(array);
        System.out.println(Arrays.toString(copy));

        //使用 Arrays 的 copyOf 方法进行数组的拷贝--使用 copyOf 方法需要创建一个新数组，新数组的长度与要拷贝的数组一样
        int[] newArray = Arrays.copyOf(array,array.length);
        System.out.println(Arrays.toString(newArray));
        //进行扩容
        int[] coPy = Arrays.copyOf(array,array.length*2);
        System.out.println(Arrays.toString(coPy));
        //拷贝某个范围
        int[] copY = Arrays.copyOfRange(array,1,3);//[1,3)
        System.out.println(Arrays.toString(copY));
        int[] cOpy = new int[array.length];
        System.arraycopy(array,0,cOpy,0,array.length);
        System.out.println(Arrays.toString(cOpy));
    }
    public static int[] copyArray(int[] array){
        int[] copy = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            copy[i] = array[i];
        }
        return copy;
    }
    public static void main4(String[] args) {
        //数组排序(冒泡排序):给定一个数组, 让数组升序 (降序) 排序
        int[] array = {1,2,31,4,15};
        System.out.println("排序前的数组:" + Arrays.toString(array));
        bubbleSort(array);
        System.out.println("排序后的数组:" + Arrays.toString(array));

        //Arrays.sort 效率比冒牌排序高
    }
    public static void bubbleSort(int[] array){
        //i 表示趟数   5个数据，比较4趟（每一趟都比上一趟少一次）
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = false;//表示不需要进行交换，是升序排列
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;//如果需要交换，即进入到循环内，就将flag改为true
                }
            }
            if (flag == false){  //如果走到这里flag还是等于false，则说明原本就是一个升序序列，直接返回
                return;
            }
        }
    }
    public static void main3(String[] args) {
        //查找数组中指定元素(顺序查找)---给定一个数组, 再给定一个元素, 找出该元素在数组中的位置
        int[] array = {1,2,3,4,5,6};
        int index = findNum(array,6);
        System.out.println(index);
        System.out.print("二分查找:");
        int index1 = binarySearch(array,6);
        System.out.println(index1);

        //如果是无序数组--先排序再查找
        int[] array1 = {1,2,31,4,15};
        System.out.println("排序前的数组:" + Arrays.toString(array1));

        Arrays.sort(array1);//使用 Arrays 的 sort 方法.默认从小到大排序

        System.out.println("排序后的数组:" + Arrays.toString(array1));

        //int index2 = binarySearch(array1,3);
        //除了自己实现一个二分查找，Array 中也有 binarySearch 方法 可以直接求出数组中要找的元素的下标
        int index2 = Arrays.binarySearch(array1,3);
        System.out.println(index2);
        //可以在指定位置查找
        int index3 = Arrays.binarySearch(array1,1,3,4);//[1,3)
        System.out.println(index3);//2
    }
    public static int findNum(int[] array,int key){  //这样的查找效率低，因为它是一个个查找的
        for (int i = 0; i < array.length; i++) {
            if (array[i] == key){
                return i;
            }
        }
        return -1;
    }
    //二分查找 - 必须是有序数组（升序或降序，以升序为例）
    //思路：先取中间位置的元素, 然后使用待查找元素与数组中间元素进行比较
    //定义一个变量left表示数组第一个元素的下标，right表示数组最后一个元素，再定义一个变量mid，表示数组的中间元素
    //如果要查找的元素与mid相等，则返回该数组元素的下标，如果要查找的元素小于mid，则只需要在 left ~ mid-1 的元素之间查找，再计算出这个区间的mid值，
    //重复进行比较，找出等于mid的元素，返回其下标，如果大于mid，则只需要在 mid+1 ~ right 之间查找（可以从left查找到right），和小于类似
    public static int binarySearch(int[] array,int key){
        int left = 0;
        int right = array.length-1;
        while (left <= right){
            int mid = (left+right) / 2;
            if (array[mid] == key){
                return mid;
            } else if (array[mid] > key) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
    public static void main2(String[] args) {
        //求数组中元素的平均值
        int[] array = {1,2,3,4,5,6};
        System.out.println(avg(array));//3.5
    }
    public static double avg(int[] array){
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        return (double) sum / (double) array.length;
    }
    public static void main1(String[] args) {
        //数组转换成字符串
        int[] array = {1,2,3,4,5,6};
        System.out.println(myToString(array));
        //用工具类 Arrays 的 toString 方法 可直接转换，比较方便
        System.out.println(Arrays.toString(array));
    }
    public static String myToString(int[] array){
        String ret = "[";
        for (int i = 0; i < array.length; i++) {
            ret += array[i];
            if (i != array.length-1){
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }
}
